public class Quick {
    public static void sort(Comparable[] a){
        sort(a, 0, a.length-1);
    }

    private static void sort(Comparable[] a, int lo, int hi){
        if (lo >= hi) return;
//        if (hi <= lo+10) {
//            for (int i = lo; i < hi; i++){
//                Comparable temp = a[i];
//                int j = i;
//                while(j >= 1 && less(temp, a[j-1])){
//                    a[j] = a[j-1];
//                    j--;
//                }
//                a[j] = temp;
//            }
//            return;
//        }
        int j = partition(a, lo, hi);
        sort(a, lo, j-1);
        sort(a, j+1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi){
        int i = lo;
        int j = hi+1;
        Comparable temp = a[lo];
        while(true){
            while (less(a[++i], temp)) if (i == hi) break;
            while (less(temp, a[--j])) if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
}
